#include <iostream>
#include <vector>

using namespace std;

class score {
public:
        int id;
        int ch;
        int math;
        friend ostream &operator<<(ostream &, const score &);
};

ostream &operator<<(ostream &os, const score &d)
{
        os << "(" << d.id << "," << d.ch << "," << d.math << ")";
        return os;
}

int sort_cmp(const score &d1, const score &d2)
{
        return d1.id < d2.id;
}

int find_cmp(const score &d)
{
        return d.ch == 98;
}

static int b_cmp(const void *key, const void *data)
{
        const int *id = (const int *)key;
        const score *d = (const score *)data;

        return *id - d->id;
}

typedef int bin_cmp(const void *key, const void *key);

template <class T>
int binsearch(vector<T> &vec, const void *key, bin_cmp *cmp)
{
        int start, end, mid;

        start = 0; end = vec.size() - 1;

        while (start <= end) {
                mid = (start + end) / 2;
                if (cmp(key, &vec[mid]) == 0) {
                        return mid;
                } else if (cmp(key, &vec[mid]) < 0) {
                        end = mid - 1;
                } else {
                        start = mid + 1;
                }
        }

        return -1;
}

int main()
{
        vector<score> vec;
        score tmp;

        for (int i = 0; i < 9; i++) {
                tmp.id = i;
                tmp.ch = 100 - i;
                tmp.math = 100 - 2 * i;
                vec.push_back(tmp);
        }

        vector<score>::iterator it;
        for (it = vec.begin(); it != vec.end(); it++) {
                if (it->id == 5) {
                        tmp.id = 99;
                        tmp.ch = 1;
                        tmp.math = 101;
                        vec.insert(it, tmp);
                        break;
                }
        }

        for (it = vec.begin(); it != vec.end(); it++) {
                cout << *it << ' ';
        }
        cout << endl;

        sort(vec.begin(), vec.end(), sort_cmp);

        for (it = vec.begin(); it != vec.end(); it++) {
                cout << *it << ' ';
        }
        cout << endl;

#if 0
        it = find_if(vec.begin(), vec.end(), find_cmp);
        if (it == vec.end()) {
                cout << "Can not find" << endl;
        } else {
                cout << *it << endl;
        }
#else
        //vector<score>::size_type ind;
        int ind;
        int id = 4;
        ind = binsearch(vec, &id, b_cmp);
        if (ind == -1) {
                cout << "Can not find" << endl;
        } else {
                cout << vec[ind] << endl;
        }
#endif

        vec.clear();

        return 0;
}
